class Solution {//leetcode103——二叉树的锯齿型层序遍历
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        queue<TreeNode*> q;
        if(root==nullptr) return ret;

        q.push(root);
        bool flag=left;
        while(!q.empty()){
            int level=q.size();
            vector<int> tmp;
            for(int i=0;i<level;i++){
                TreeNode* t=q.front();
                tmp.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);

                q.pop();
            }
            if(flag==right) {
                reverse(tmp.begin(),tmp.end());
                flag=left;
            }
            else if(flag==left) flag=right;
            ret.push_back(tmp);
        }
        return ret;
    }
    private:
        bool right=true;
        bool left=false;
};